In transmission of data packets over packet based networks, there is a possibility of packet loss, such that it may be assumed that a certain percentage of packets are lost on any packet based network. Packets may be lost due to channel conditions and/or due to application operation, for example late tuning onto a data transmission. In some cases, such as transfer of a file, the loss of even a small percentage of the transmitted data prevents the use of the entire file.
In some cases, redundant data is transmitted along with the transmitted data, such that even if some of the transmitted data is lost, the original data can be reconstructed from the data that was received. One method of redundancy is referred to as forward error correction (FEC). In accordance with a simple FEC code, the protected data is included in a single source word (also referred to as a block), divided into a set X of k source elements (original elements). For the single source word, n>k code elements (referred to also as FEC elements), of the same size as the source elements, are generated, in order to represent the source words in a protected manner. The n code elements are referred to together as a code word. The elements may be of different sizes, such as single bits or packets. A receiver needs to receive correctly any k+z elements (z>=0) from the transmitted code word in order to reconstruct the source word. When z=0 the code is considered optimal.
Various coding methods of generating the code elements from the source elements, are known in the art. One of the attributes of coding methods is the ratio k/n, which is referred to as the code rate. The code rate used depends on the expected data loss rate, the importance of the data and the available bandwidth.
Generally, there exist efficient coding methods only for several coding rates. When it is desired to have a code rate that does not have an efficient coding method, a method with a lower code rate (i.e., a higher n for the same k) is used to generate the code elements, and then some of the code elements are dropped The dropped code elements are referred to as punctured elements. In some cases, punctured elements are retransmitted, instead of or in addition to other code elements not correctly received.
If the source word is a subset of the code word (i.e., X is a subset of Y), the code is referred to as a systematic code. The portion of the code word not included in the source word is referred to as a parity word. Codes in which the source word is not a subset of the code word are referred to as non-systematic codes.
When possible, it is considered advantageous to include an entire data file in a single source word, for which a single code word is generated. The available codes, however, such as the Reed Solomon (RS) code, require large processing resources when the source word is large. In order to reduce the processing power required, in one-dimensional codes (known also as single dimension codes), the original data is divided into a plurality of source words and code words are generated for each source word independently.
As the size of the original data increases, the number of source words increases, and therefore the chances of successfully reconstructing the original data decreases, since all the source words need to be reconstructed independently. Excess elements (beyond k+z) received for one of the source words does not aid in the reconstruction of other source words for which a sufficient number of elements was not received.
In an exemplary two-dimensional code, the original data is arranged in a two-dimensional array. Each row and each column of the array is viewed as a separate source word, for which a code word is generated. In the data reconstruction, the elements of each row code word which is successfully reconstructed can be used in the reconstruction of column code words and vice versa. An iterative “column-row” reconstruction method is generally used to reconstruct the data.
For substantially the same complexity (i.e., processing resources), the two-dimensional FEC requires less bandwidth than the one-dimensional FEC. For high-loss transmission links and for short original data, the two-dimensional FEC becomes inefficient.